package com.datastructure.test.fournumber;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.stream.Collectors;

public class FourNumber {

    public static void main(String[] args) {
        FourNumber fourNumber = new FourNumber();
        ArrayList<Integer> nums = new ArrayList<>();
        nums.add(2);
        nums.add(0);
        nums.add(-2);
        nums.add(3);
        nums.add(-3);
        nums.add(0);
        ArrayList<ArrayList<Integer>> fournumber = fourNumber.fournumber(nums, 0);
        System.out.println(fournumber);
    }

    public ArrayList<ArrayList<Integer>> fournumber (ArrayList<Integer> nums, int target) {
        // write code here
        ArrayList<Integer> collect = (ArrayList<Integer>)nums.stream().sorted().collect(Collectors.toList());
        int[] num = new int[collect.size()];
        for (int i = 0; i < collect.size(); i++) {
            num[i]=collect.get(i);
        }
        return threeSum(num,target);
    }

    public ArrayList<ArrayList<Integer>> threeSum(int[] num,int target) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        if(num==null || num.length<4){
            return res;
        }
        for(int i=0;i<num.length;i++){
            if(num[i]>target){
                break;// 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            }
            if(i>0 && num[i]==num[i-1]){
                continue;// 去重
            }
            for(int j=i+1;j< num.length;j++){
                if(num[j]>target){
                    break;// 如果当前数字大于0，则三数之和一定大于0，所以结束循环
                }
                if(j>i+1 && num[j]==num[j-1]){
                    continue;// 去重
                }
                int L=j+1;
                int R=num.length-1;

                while(L<R){
                    int sum=num[i]+num[L]+num[R]+num[j];
                    if(sum==target){
                        ArrayList<Integer> list=new ArrayList<>();
                        list.add(num[i]);
                        list.add(num[L]);
                        list.add(num[R]);
                        list.add(num[j]);
                        res.add(list);

                        while(L<R && num[L]==num[L+1]){
                            L++;
                        }
                        while(L<R && num[R]==num[R-1]){
                            R--;
                        }
                        //不等于的时候再加1
                        L++;
                        R--;
                    }
                    else if(sum>target){
                        R--;
                    }
                    else {
                        L++;
                    }
                }
            }
        }
        return res;
    }
}
